//地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一
//格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但
//它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？ 
//
// 
//
// 示例 1： 
//
// 输入：m = 2, n = 3, k = 1
//输出：3
// 
//
// 示例 2： 
//
// 输入：m = 3, n = 1, k = 0
//输出：1
// 
//
// 提示： 
//
// 
// 1 <= n,m <= 100 
// 0 <= k <= 20 
// 
// Related Topics 深度优先搜索 广度优先搜索 动态规划 
// 👍 330 👎 0


package leetcode.editor.cn1;

//Java：机器人的运动范围

import java.util.ArrayDeque;
import java.util.Queue;

/**
 * 地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。
 * 请问该机器人能够到达多少个格子？
 * <p>
 * 输入：m = 2, n = 3, k = 1
 * 输出：3
 * <p>
 * 输入：m = 3, n = 1, k = 0
 * 输出：1
 * <p>
 * 解题思路：
 * 1、深度优先
 * 2、广度优先
 */
public class JiQiRenDeYunDongFanWeiLcof_1027 {
    public static void main(String[] args) {
        Solution solution = new JiQiRenDeYunDongFanWeiLcof_1027().new Solution();
        // TO TEST
        System.out.println(solution.movingCount(2, 3, 1));
        System.out.println(solution.movingCount(3, 1, 0));
        // 15
        System.out.println(solution.movingCount(16, 8, 4));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int movingCount(int m, int n, int k) {
//            boolean[][] visited = new boolean[m][n];
//            return dsf(0, 0, m, n, k, visited);
            return bsf(m, n, k);
        }

        /**
         * 深度优先
         *
         * @param i
         * @param j
         * @param m
         * @param n
         * @param k
         * @param visited
         * @return
         */
        public int dsf(int i, int j, int m, int n, int k, boolean[][] visited) {
            if (i >= m || i < 0 || j >= n || j < 0 || visited[i][j] || isLargeK(i, j, k))
                return 0;
            visited[i][j] = true;
            return 1 + dsf(i + 1, j, m, n, k, visited) + dsf(i, j + 1, m, n, k, visited);
        }

        /**
         * 广度优先遍历
         *
         * @param m
         * @param n
         * @param k
         * @return
         */
        public int bsf(int m, int n, int k) {
            boolean[][] visited = new boolean[m][n];
            Queue<int[]> queue = new ArrayDeque<>();
            // 将0,0加入队列
            queue.offer(new int[]{0, 0});
            int sum = 0;
            while (!queue.isEmpty()) {
                // 取出队列第一个节点
                int[] ele = queue.poll();
                int tx = ele[0], ty = ele[1];

                if (tx >= m || tx < 0 || ty >= n || ty < 0 || visited[tx][ty] || isLargeK(tx, ty, k))
                    continue;
                // 将一层的节点加入队列
                visited[tx][ty] = true;
                queue.offer(new int[]{tx + 1, ty});
                queue.offer(new int[]{tx, ty + 1});
                sum++;
            }
            return sum;
        }

        /**
         * 判断数位之和是否大于k
         *
         * @param i
         * @param j
         * @param k
         * @return
         */
        public boolean isLargeK(int i, int j, int k) {
            int sum = 0;
            while (i > 0) {
                sum = sum + i % 10;
                i = i / 10;
            }

            while (j > 0) {
                sum = sum + j % 10;
                j = j / 10;
            }

            if (sum > k)
                return true;
            return false;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}
